#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
using namespace std;

// 二叉树
typedef struct TNode
{
    int data;
    TNode *left, *right;
} * Tree, TNode;

//visit
void visit(Tree T)
{
    printf("%d ", T->data);
}

// 先序遍历
void Preorder(Tree T)
{
    if (T != NULL)
    {
        visit(T);
        Preorder(T->left);
        Preorder(T->right);
    }
}
// 中序遍历
void Inorder(Tree T)
{
    if (T != NULL)
    {
        Inorder(T->left);
        visit(T);
        Inorder(T->right);
    }
}
// 后续遍历
void Postorder(Tree T)
{
    if (T != NULL)
    {
        Postorder(T->left);
        Postorder(T->right);
        visit(T);
    }
}

// 获取指定结点的所有祖先结点
bool GetAncestors(Tree T, int e)
{
    if (!T)
        return false;
        
    if (T->data == e)
        return true;
    
    if (GetAncestors(T->left, e) || GetAncestors(T->right,e)) {
        printf("find ancestor: %d\n", T->data);
        return true;
    }

    return false;
}

// 测试用
TNode *NewNode(int e)
{
    TNode *s = (TNode *)malloc(sizeof(TNode));
    s->data = e;
    s->left = NULL;
    s->right = NULL;
    return s;
}

// 层序遍历
void PrintTree(Tree T)
{
    queue<TNode *> q;
    if (T != NULL)
    {
        q.push(T);
    }
    while (!q.empty())
    {
        printf("%d ", q.front()->data);
        if (q.front()->left != NULL)
            q.push(q.front()->left);

        if (q.front()->right != NULL)
            q.push(q.front()->right);
        q.pop();
    }
}

int main(int argc, char const *argv[])
{
    Tree T;
    T = NewNode(0);
    T->left = NewNode(1);
    T->right = NewNode(2);
    T->left->left = NewNode(3);
    T->left->right = NewNode(4);
    T->right->left = NewNode(5);
    printf("Level traversal:\n");
    PrintTree(T);
    printf("\n");
    printf("Preorder traversal:\n");
    Preorder(T);
    printf("\n");
    printf("Inorder traversal:\n");
    Inorder(T);
    printf("\n");
    printf("Postorder traversal:\n");
    Postorder(T);
    printf("\n");

    GetAncestors(T,5);
    return 0;
}
